package com.yuqingsong.algorithm.tree;

import java.util.Comparator;

public class BinaryTree<K, V> implements SearchTree<K, V> {

	/**
	 * 用于创建节点
	 */
	private NodeBuilder<K, V> builder;

	/**
	 * 根节点
	 */
	private BsTreeNode<K, V> root;

	/**
	 * 用于比较key
	 */
	private Comparator<? super K> comp;

	@Override
	public V search(K key) {
		if (key == null) {
			return null;
		}
		BsTreeNode<K, V> current = root;
		while (current != null) {
			int c = comp.compare(key, current.key());
			if (c == 0) {
				return current.value();
			}
			current = c < 0 ? current.left() : current.right();
		}
		return null;
	}

	public void insert(K k, V v) {
		BsTreeNode<K, V> node = builder.builder(k, v);
		if (root == null) {
			root = node;
			return;
		}
		/*
		 * 插入的节点总是添加到叶子节点上。 下面的循环是找到要插入节点的父节点。
		 */
		BsTreeNode<K, V> parent = null;
		BsTreeNode<K, V> current = root;
		while (current != null) {
			parent = current;
			// 插入的节点小于当前节点
			if (comp.compare(k, current.key()) < 0) {
				current = current.left();
			} else {
				current = current.right();
			}
		}

		if (comp.compare(k, parent.key()) < 0) {
			parent.setLeft(node);
		} else {
			parent.setRight(node);
		}

	}

	public void print() {
		print(this.root);
	}

	public static <K, V> void print(BsTreeNode<K, V> node) {
		if (node != null) {
			print(node.left());
			System.out.println(node);
			print(node.right());
		}
	}

	@Override
	public BsTreeNode<K, V> min() {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public BsTreeNode<K, V> max() {
		// TODO Auto-generated method stub
		return null;
	}

}
